类似于poj1185，但是这里的影响范围是它曼哈顿距离为$2$的格子，也就是说处理状态变得复杂了很多。
设$dp(i, st(j), st(k))$为第$i$行用状态$k$，第$i-1$行用状态$j$的最优值。那么转移方程即为：
$$dp(i, st(j), st(k)) = max(dp(i, st(t), st(j)) + num(k))$$
怎么处理状态？先处理每行可行方案，1、不能有三个连续的摆放 2、不能有两个摆放之间距离为$2$
按位DP的时候，$i$上面一行对$i$行的影响只有两个方格，具体是哪个画图就知道。$i$上面第二行对$i$行的影响只有一个方格，同样具体是哪个画图就知道。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "soldier"
using namespace std;
const int MAXN = 100 + 5;
int n, m, num[200 + 5], cur[MAXN], st[200 + 5], dp[MAXN][200 + 5][200 + 5], top;
int js(int x) {
int ret = 0;
while (x) {
ret++;
x&=(x-1);
}
return ret;
}
int check(int x) {
int tot = 0, tot2 = 0;
while (x) {
if (x&1) {
if (tot2==1&&tot!=-1) return false; else if (tot2>=1) tot = 0;
tot2 = 0, tot++;
if (tot>=3) return false;
} else {
tot2++;
if (tot==0) tot = -1;
}
x>>=1;
}
if (tot>=3) return false;
return true;
}
int check2(int up, int down) {
int i = 0;
while (up) {
if (up&1) {
if (i-1>=0&&(down>>(i-1))&1) return false;
if (i+1<m&&(down>>(i+1))&1) return false;
}
up>>=1, i++;
}
return true;
}
bool fit(int s1, int h) {return (s1&cur[h]) ? false : true;}
void clean() {
top = 1, ms(dp, -1), st[top] = 0;
}
void solve() {
clean();
for (int i=1;i<(1<<m);i++) if (check(i)) st[++top] = i, num[top] = js(i);
for (int i=1;i<=n;i++) {
cur[i] = 0;
for (int j=1;j<=m;j++) {
int x; scanf("%d", &x);
if (!x) cur[i] += (1<<(j-1));
}
}
for (int i=1;i<=top;i++) {
if (fit(st[i], 1)) dp[1][i][1] = num[i];
}
for (int hi=2;hi<=n;hi++) {
for (int i=1;i<=top;i++) {
if (fit(st[i], hi)) {
for (int j=1;j<=top;j++) {
if (check2(st[j], st[i])&&fit(st[j], hi-1)) {
for (int k=1;k<=top;k++) {
if (st[k]&st[i]) continue;
if (dp[hi-1][j][k]==-1) continue;
if (check2(st[k], st[j])&&fit(st[k], hi-2)) dp[hi][i][j] = max(dp[hi][i][j], dp[hi-1][j][k] + num[i]);
}
}
}
}
}
}
int ans = 0;
for (int hi=1;hi<=n;hi++) {
for (int i=1;i<=top;i++) {
for (int j=1;j<=top;j++) {
ans = max(ans, dp[hi][i][j]);
}
}
}
printf("%d\n", ans);
}
int main() {
freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
while (scanf("%d%d", &n, &m)==2&&n&&m) solve();
fclose(stdin); fclose(stdout);
return 0;
}
Soldier
1s
Problem Description
郑厂长不是正厂长
也不是副厂长
他根本就不是厂长
事实上
他是带兵打仗的团长
一天，郑厂长带着他的军队来到了一个n*m的平原准备布阵。
根据以往的战斗经验，每个士兵可以攻击到并且只能攻击到与之曼哈顿距离为2的位置以及士兵本身所在的位置。当然，一个士兵不能站在另外一个士兵所能攻击到的位置，同时因为地形的原因平原上也不是每一个位置都可以安排士兵。
现在，已知n,m 以及平原阵地的具体地形，请你帮助郑厂长计算该阵地,最多能安排多少个士兵。
Input
输入包含多组测试数据；
每组数据的第一行包含2个整数n和m (n <= 100, m <= 10 )，之间用空格隔开；
接下来的n行，每行m个数，表示n*m的矩形阵地，其中1表示该位置可以安排士兵，0表示该地形不允许安排士兵。
Output
请为每组数据计算并输出最多能安排的士兵数量，每组数据输出一行。
Sample Input
6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Sample Output
2
